package gitdemo1.git3.day;

public class Kmp {
    public static void main(String[] args) {
        int i = Kmp("flower", "er");
        System.out.println(i);

    }
    //s是否包含m，如果有就返回在s的起始位置
    public static int  Kmp(String s,String m){
        if(s==null||m==null||s.length()<m.length()||m.length()<1){
            return -1;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = m.toCharArray();
        int i1=0;
        int i2=0;
        int nexts[]= getWayNexts(str2);

        while(i1<str1.length&&i2<str2.length){
            //相同就都一起往下面走
            if(str1[i1]==str2[i2]){
                i1++;
                i2++;
            }else if(nexts[i2]==-1){//如果i2已经走到头了，那么i1就要换下一个了
                i1++;
            }else{
                i2=nexts[i2];//如果i2还有那么就从i2要等于当前i2的最大前缀
            }
        }

        return i2==str2.length? i1-i2:-1;
    }

    private static int[] getWayNexts(char[] str2) {
        if(str2.length==1){
            return new int[]{-1};
        }
        //定义一个最长前缀的数组
        int nexts[]=new int[str2.length];
        //表示当前最大前缀的长度
        int cn=0;
        nexts[0]=-1;
        nexts[1]=0;
        int i=2;
        while(i < str2.length) {
            //如果相等就增加一个
            if(str2[cn]==str2[i-1]){
                nexts[i++]=++cn;
            }else if(nexts[cn]==-1){
                //就是没有了
                nexts[i++]=0;
            }else{
                //当前没有就往之前找
                cn=nexts[cn];
            }
        }

        return nexts;

    }


}
